The invention relates generally to the field of shape representation, and in particular to representing, rendering, and manipulating shapes with distance fields.
Surface Representations
A representation of xe2x80x9cshapexe2x80x9d of an object or model is required in many fields such as computer-aided design and manufacturing, computational physics, physical modeling, and computer graphics. Three common representations for shape are parametric surface models, implicit surfaces, and sampled volume data.
Parametric Surface Models
Parametric surface models define the surfaces of an object as a collection of primitives such as polygons, spline patches, or subdivision surfaces that are defined parametrically. Most graphics systems use a parametric representation. As stated by Alyn Rockwood in xe2x80x9cThe displacement method for implicit blending surfaces in solid models,xe2x80x9d ACM Transactions on Graphics, Vol. 8, No. 4, 1989, xe2x80x9cparametric surfaces are usually easier to draw, tessellate, subdivide, and bound, or to perform any operation on that requires a knowledge of xe2x80x98wherexe2x80x99 on the surface.xe2x80x9d However, parametric surface models are difficult to combine, sculpt, or deform. Moreover, parametric surface models cannot be used for solid objects because they do not represents the interior of objects.
Implicit Surfaces
Implicit surfaces are represented by an implicit function, ƒ(x). The function is defined over the space including the surface. The surface of the object is expressed as an iso-surface of an implicit function: i.e., ƒ(x)=c. Implicit surfaces can represent object interiors, can easily blend together, can morph between object shapes, and can perform constructive solid geometry (CSG) operations on objects. Implicit surfaces can also detect inside versus outside of objects. However, as stated by Bloomenthal in Introduction to Implicit Surfaces, Morgan Kaufman Publishers, 1997, while the xe2x80x9cnatural conversion from the parametric (2D) space of a surface to the geometric (3D) space of an object is a fundamental convenience, and partially accounts for the popularity of parametric surfaces . . . there is no comparable mechanism for implicit surfaces.xe2x80x9d In other words, given the equation defining an implicit surface it is hard to locate points on the surface in object space. In addition, it can be difficult to find implicit functions for some arbitrary objects.
Sampled Volume Data
Sampled volume data represent objects and models in an array of sampled intensity values on a regular or irregular grid. Volume data are usually generated from 3D image data or from numerical simulation. Like implicit surfaces, sampled volume data represent object interiors, and the sampled volume data can be used in many of the same ways that implicit surfaces are used. However, the accuracy of the object representation is limited by the resolution of the sampling. Sampled data are usually intensity-based so that an object is distinguished from the background and from other objects by the sampled intensity values. In general, this means that the sampled intensities change abruptly at object surfaces to introduce high spatial frequencies into the data. High sampling rates are required to avoid aliasing artifacts and jagged edges in rendered images. Because high sampling rates increase memory requirements and rendering times, the quality of the represented surface must be traded-off with memory requirements and rendering speed.
Distance Fields and Distance Maps
A scalar field is a single-valued N-dimensional function that is defined over a given region. A distance field is a scalar field that represents the xe2x80x9cdistancexe2x80x9d to a surface, xcex4S, of an object, S. A xe2x80x9cdistancexe2x80x9d is defined for each p contained in the domain of the field by D(p, S)=minabs{∥pxe2x88x92q∥}, for all points q on the surface xcex4S, where minabs{A} determines the signed element of a set A with the minimum absolute magnitude, and ∥xcx9c∥ represents a distance metric with the following characteristics: the distance metric has a value of zero everywhere on xcex4S and the metric is signed to permit the distinction between the inside and the outside of S. A surface at a non-zero iso-surface of the distance field can be easily specified by adding a scalar offset to the distance field.
A sampled distance field is a set of values sampled from the distance field along with either an implicit or explicit representation of the sampling location. The sampled values can include distance values and associated distance computations such as the gradient of the distance field and/or other partial derivatives of the distance field.
One example of a distance metric is the Euclidean distance in which the distance field at any point p becomes the signed Euclidean distance from p to the closest point on the object surface. A distance map is defined to be the sampled Euclidean distance field where the sample locations lie on a regular grid. Distance maps have been used in several applications.
For example, Lengyel et al. used distance maps for robotic path planning in xe2x80x9cReal-time robot motion planning using rasterizing computer graphics hardware,xe2x80x9d SIGGRAPH, pp. 327-335, 1990. Others have used distance maps for morphing between two objects. See xe2x80x9cDistance field manipulation of surface models,xe2x80x9d Payne et al. in IEEE Computer Graphics and Applications, January, 1992 for an example. Distance maps have also been used for generating offset surfaces as discussed by Breen et al. in xe2x80x9c3D scan conversion of CSG models into distance volumes,xe2x80x9d Proceedings of the IEEE Volume Visualization Symposium, 1998. Gibson used distance maps to represent precision surfaces for volume rendering in xe2x80x9cUsing distance maps for smooth surface representation in sampled volumes,xe2x80x9d Proceedings of the IEEE Volume Visualization Symposium, 1998. Four methods for generating distance maps from binary sampled volume data are compared by Gibson in xe2x80x9cCalculating distance maps from binary segmented data,xe2x80x9d MERL Technical Report TR99-26, April, 1999.
Because the Euclidean distance field varies slowly across surfaces, distance maps do not suffer from the aliasing problems of sampled intensity volumes. Smooth surfaces can accurately be reconstructed from relatively coarse distance maps as long as the surface has low curvature. However, because distance maps are regularly sampled, they suffer from some of the same problems as sampled volumes. For example, the size of the distance map is determined by a combination of the volume of the object and the finest detail that must be represented. Hence, volumes that have some fine detail surfaces require large distance maps, even when only a small fraction of the volume is occupied by the fine-detail surfaces. In addition, distance maps are typically rendered by using volume rendering techniques. Volume rendering techniques can be very slow, and may require many seconds or minutes per frame for high quality rendering of reasonably sized volumes.
Spatial Data Structures for Hierarchical Object Representation
A number of methods are known for hierarchically organizing spatial data for efficient memory usage, rendering, or physics modeling. Examples of spatial data structures are presented in two books by Samet, xe2x80x9cThe Design and Analysis of Spatial Data Structures,xe2x80x9d and xe2x80x9cApplications of Spatial Data Structures,xe2x80x9d both published by Addison-Wesley in 1989.
Octrees recursively decompose three-dimensional space into eight equal-sized octants or nodes in order to organize data hierarchically. Region octrees divide data into nodes corresponding to uniform regions of the volume image. When the image data is binary, the resultant tree has two types of nodes, interior nodes and exterior nodes. Three-color octrees classify nodes as being interior, exterior or boundary nodes, where boundary nodes intersect object surfaces. Boundary nodes are subdivided recursively to the highest resolution of the volume data. Object surfaces are rendered by drawing the boundary leaf nodes.
Three-color octrees have been applied to volume data to reduce the amount of storage required for interior and exterior regions, and to provide an efficient structure to speed up rendering and collision detection. However, representing surfaces by boundary nodes on a uniform grid results in problems similar to those found in sampled volumes. Rendered images are subject to aliasing artifacts unless surfaces are sampled at very high frequencies. The sampling rate, which corresponds to the resolution of the boundary nodes, is determined by the highest required resolution of the rendered image rather than the amount of detail present in the surface. Hence, a three-color octree representation can require a significant amount of memory even for relatively flat surfaces.
Converting Sampled Volume Data to a Polygon Model
The Marching Cubes algorithm and its successors, first described by Lorensen and Cline in xe2x80x9cMarching Cubes: a high resolution 3D surface construction algorithm,xe2x80x9d in Computer Graphics, 21(4) pp. 163-169, 1987, is the most commonly used method for fitting a triangle model to the iso-surface of a regularly sampled volume. For each cell containing the iso-surface, a table lookup determines a set of triangles that approximate the iso-surface within the cell. This method is limited to volumes sampled on a rectilinear grid because of their approaches for resolving topological ambiguities and guaranteeing crackless surfaces.
Gibson presented a method for converting a binary sampled volume to a triangle model in xe2x80x9cConstrained Elastic SurfaceNets: generating smooth surfaces from binary segmented dataxe2x80x9d in the Proceedings of MICCAI""98, pp. 888-898, 1998. That method fits a linked net of nodes over the surface of a binary object in a regularly sampled volume. The positions of the nodes are then adjusted to smooth out the shape of the surface net subject to constraints defined by the original node placement. That method does not fit surfaces to gray-scale data.
Converting Point Clouds to Parametric Surfaces
Hoppe et al, in xe2x80x9cSurface reconstruction from unorganized pointsxe2x80x9d, Proc. SIGGRAPH""92, pp. 71-78, 1992, and xe2x80x9cPiecewise smooth surface reconstructionxe2x80x9d, Proc. SIGGRAPH""94, pp. 295-302, 1994, describe a method that converts a set of unorganized points to a triangular model and subsequently fits a subdivision surface to the output triangle model. The method generates a distance map from the point cloud and then uses Marching Cubes to generate the triangle model. This method is limited by the resolution of the distance map and by the accuracy of the distance map that can be estimated from the unorganized points.
Converting Implicit Surfaces to Triangles
Bloomenthal, in xe2x80x9cPolygonization of implicit surfaces,xe2x80x9d Technical Report, Xerox Parc, EDL-88-4, December, 1988, discloses a method for converting a surface expressed as a single implicit function to triangles. In an intermediate temporary data structure, the function is evaluated at vertices of cells intersecting the surface. The intermediate representation is polygonized by joining points on the twelve cell edges that are on the desired iso-surface expressed by the implicit function. He tracks the surface by propagating cells beginning at an xe2x80x9cinitial seed cell that intersects the surface, and is small in comparison with surface detail.xe2x80x9d Alternatively, he converges to the surface by only xe2x80x9csubdividing those cubes that intersect the surface.xe2x80x9d Rendering and editing the temporary data structure are not described.
Rendering Distance Maps
Distance maps can be rendered directly without converting them to a parametric model as described by Gibson in xe2x80x9cUsing distance maps for smooth surface representation in sampled volumes,xe2x80x9d Proceedings of the IEEE Volume Visualization Symposium, 1998. However, the volume rendering approach used is very slow for reasonably large volumes.
Surface Editing for Parametric Surfaces
Editing parametric surfaces is a challenging problem. The most commonly used parametric surfaces in engineering design are non-uniform rational B-spline (NURB) surfaces, for which surface editing is performed by a process called trimming. However, as stated by DeRose et al., in xe2x80x9cSubdivision surfaces in character animation,xe2x80x9d Proc. SIGGRAPH""98, pp. 85-94, 1998, this process xe2x80x9cis expensive and prone to numerical error.xe2x80x9d
A number of methods for editing other types of parametric surfaces have been presented, but in general, they are complex and non-intuitive, and it is difficult to control the quality of the edited surface. For example, Naylor represents solid objects and tools as a binary space partitioned (BSP) tree in xe2x80x9cSCULPT: an interactive solid modeling tool,xe2x80x9d Proc. Graphics Interface""90, pp. 138-148, 1990. He performs union, difference and intersection operations between a tool and an object by locating the tree within the object BSP tree and editing the object tree. He illustrates how difficult it is to sculpt solid models of even relatively simple objects. The examples of carved objects that are presented have low resolution and rough edges around the carved regions.
Khodakovsky and Schroder presented a method for carving subdivision surfaces in xe2x80x9cFine level feature editing for subdivision surfacesxe2x80x9d in the Proceedings of Solid Modeling and Applications, pp. 203-211, 1999. Again, their approach is quite complex, even for relatively simple editing operations on relatively simple object models. It is hard to imagine using this method for free-form sculpting.
Raviv and Elber recently described a method for representing an object as a collection of scalar uniform trivariate B-splines defined over a set of arbitrarily oriented cubic patches. The B-splines are controlled by a large number of control coefficients (typically 215), and the object shape is edited by modifying these coefficients. The method cannot provide fine detail editing such as corners and small holes without excessive memory and computation times. The results presented in the paper show poor surface detail and the reported editing and rendering times are very slow.
Sculpting Sampled Volume Data
Several systems have been developed for sculpting volumetric data. These systems represent objects as density maps, where a density of one corresponds to object interiors and a density of zero corresponds to object exteriors. These systems typically include a boundary region around each object where the density varies from zero to one in order to avoid aliasing artifacts during rendering. All of these systems use a regularly sampled volume for volume editing, which involves adding or subtracting material from a non-deformable volume object. In addition, Barentzen discusses the use of a three-color octree for storing and rendering the density map. For details, see: Galyean and Hughes, xe2x80x9cSculpting: an interactive volumetric modeling technique,xe2x80x9d Proceedings SIGGRAPH""91; Wang and Kaufman, xe2x80x9cVolume sculpting,xe2x80x9d Proceedings 1995 Symposium on Interactive 3D Graphicsxe2x80x9d; Avila and Sobierajski, xe2x80x9cA haptic interaction method for volume visualization,xe2x80x9d Proceedings IEEE Volume Visualization""96; and Baerentzen, xe2x80x9cOctree-based volume sculpting,xe2x80x9d Proceedings Late-breaking Hot Topics, IEEE Visualizaiton""98.
There are several limitations to these systems. First, the use of filtered boundary regions reduces aliasing but results in smoothed and rounded corners and edges. The smoothing is a result of the filters used on the data and could be reduced by using distance maps instead of low-pass filters. Second, because the objects are stored in a regular grid, the resolution of the object surface is limited by the grid resolution. Hence, density maps require large volumes when there is fine detail present, even when only a small fraction of volume is occupied by fine-detail surfaces. Third, because of the large volume size, rendering of density maps is slow. While Barentzen""s proposed octree-based density map reduces these problems, the problems of three-color octrees apply. In addition, editing is limited by the pre-determined highest resolution of the octree.
Schroeder et al, in xe2x80x9cImplicit modeling of swept volumes and swept surfaces,xe2x80x9d U.S. Pat. No. 5,542,036, describe a method for computing a computer model of swept volumes. A composite distance map is computed by assigning, to each sample point, the minimum distance to the object over time as the object is swept through space. A surface of the swept volume is converted to triangles via Lorensen and Cline""s Marching Cubes algorithm. The distance map is of fixed resolution and is regularly sampled so the problems of distance maps apply.
Colbum presents a method for generating fillets and rounds on the edges and corners of solid models that has some similarities to editing methods for volume data in xe2x80x9cMethod for global blending of computer modeled solid objects using a convolution integral,xe2x80x9d U.S. Pat. No. 4, 791,583. In that method, solid objects are represented in an octree and each boundary cell is assigned a value determined by the percent of its volume occupied by the object. Rounding is achieved by evaluating the convolution of cell values with a spherical Gaussian filter at points along rays that are perpendicular to the original object surface. The rounded surface is reconstructed through the point on each ray where the convolution evaluates to a constant iso-value. The method is specifically limited to adding rounds and fillets on the edges and corners of solid models. In addition, the resolution of the object representation is limited by the size of the boundary cells and hence limits the accuracy of the reconstructed surface.
Summary of problems with the prior art
Each of the three common surface representations discussed above has limitations. Parametric surface models do not represent interiors and do not provide an easy means for detecting inside vs. outside. Implicit surfaces do not have a natural conversion from the expression for the surface to points in 3D space and hence they are harder to render than parametric surfaces. Sampled volume data are subject to artifacts and hence must be sampled at high frequencies in order to represent surfaces accurately. These high sampling rates require large amounts of memory and long rendering times.
Distance maps can reduce aliasing artifacts in sampled volumes, but because distance maps are sampled on a regular grid, they still require a trade-off between memory requirements and the finest detail that can be represented. In addition, volume rendering of distance maps is slow, limiting real-time interactivity. The three-color octree could be used with distance maps to improve rendering rates and reduce the amount of storage necessary for object interiors and exteriors.
It is desirable to further reduce the amount of storage by allowing boundary leaf nodes whose resolution could be tailored to local surface detail. For example, it would be desirable to be able to represent a fine curve on a large, relatively smooth object without having to represent the surface of the entire object at excessively high resolution. Hence, there is a need for a representation of sampled distance fields that is detail-directed, so that the resolution of boundary leaf nodes is adapted to local detail in the surface.
As discussed above, volumetric representations are well suited for editing and sculpting graphical objects. However, existing density map methods are problematic because of excessive smoothing of edges and corners and because of data storage and rendering requirements. In addition, because the resolution of the sampled data is pre-determined, the detail that can be achieved during editing is limited before editing begins.
Hence there is a need for a detail-directed volume representation for sculpting graphical objects. The representation should be flexible so that if a sharp corner were generated or removed during editing, the representation would locally adapt to resolution requirements. As well as the object representation, techniques for editing, interacting with, and rendering objects represented by the structure are required. In addition, methods for converting the new representation to and from standard representations are required.
Provided is a method that generates a detail directed hierarchical representation of a distance field that is enclosed by a bounding box. The method begins by partitioning the bounding box enclosing the distance field into cells. Each cell has a size corresponding to detail of the distance field and a location with respect to the bounding box.
Next, the distance field is sampled to obtain a set of values for each cell. A method for reconstructing the portion of the distance field enclosed by the cell is specified for each cell. The location and size, the set of values, and the method for reconstructing for each cell is stored in a memory to enable reconstruction of the distance field by applying the reconstruction methods of the cells to the values.
The partitioning can be performed in a top-down or bottom-up manner. In the top-down manner, the bounding box is partitioned such that each partitioning yields smaller sized cells until a portion of the distance field represented by each cell can substantially be reconstructed by the method for reconstructing to a predetermined surface representation error.
In the bottom-up manner, the bounding box is first partitioned into equal sized cells such that a portion of the distance field represented by each cell can substantially be reconstructed by the method for reconstructing to a predetermined surface representation error. Then, groups of neighboring cells are combined into larger cells as long as the portion of the distance field enclosed by the larger cell can substantially be reconstructed to the surface representation error.
In one aspect, the invention provides a data structure representation of the sampled distance field that is efficient in terms of memory usage while allowing the distance field to be represented with arbitrary accuracy. More particularly, in the hierarchical distance field, the distance field is sampled at high enough resolution so that it can be reconstructed to a predetermined accuracy and the sampling is detail-directed so that higher sampling rates are used in regions where the distance field has more detail and lower sampling rates are used in regions where the distance field varies smoothly.